/**
 * 
 * @author 魏康威
 *
 */
public class SortList {
	public static ListNode sortList(ListNode head) {
		// 0个节点 || 1个节点
		if (head == null || head.next == null)
			return head;
		// >= 2个节点
		ListNode first = head, second = null, mid = getMid(head);
		second = mid.next;
		mid.next = null; // 将链表分为两段！！！！
		//递归
		first = sortList(first);
		second = sortList(second);
		return merge(first, second);
	}

	// 排序
	public static ListNode merge(ListNode first, ListNode second) {
		if (first == null) {
			return second;
		}
		if (second == null) {
			return first;
		}

		ListNode res = new ListNode(0);
		ListNode curr = res;// 控制新链表顺序的point

		while (first != null && second != null) {
			if (first.val < second.val) {
				curr.next = first;
				curr = curr.next;
				first = first.next;
			} else {
				curr.next = second;
				curr = curr.next;
				second = second.next;
			}
		}

		if (first != null) {
			curr.next = first;
		}
		
		if (second != null) {
			curr.next = second;
		}

		return res.next;
	}

	// 获取链表的中间节点
	public static ListNode getMid(ListNode head) {
		ListNode slow = head, fast = head.next;

		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}

		return slow;
	}

	public static void main(String[] args) {
		ListNode list = new ListNode(-1);
		ListNode node1 = new ListNode(-2);
		ListNode node2 = new ListNode(1);
		ListNode node3 = new ListNode(8);
		ListNode node4 = new ListNode(4);
		ListNode node5 = new ListNode(10);
		ListNode node6 = new ListNode(3);
		ListNode node7 = new ListNode(7);
		ListNode node8 = new ListNode(5);
		
		list.next = node1;
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		node5.next = node6;
		node6.next = node7;
		node7.next = node8;
		
		ListNode listNode = sortList(list);
		while (listNode != null) {
			System.out.println(listNode.val);
			listNode = listNode.next;
		}
	}
}

class ListNode {
	int val;
	ListNode next;

	ListNode(int x) {
		val = x;
	}
}
